package com.yun.algorithmproblem.leetcode;

import java.util.Map;
import java.util.TreeMap;

public class Leetcode2070 {

    public static void main(String[] args) {
        Leetcode2070 obj = new Leetcode2070();
        obj.maximumBeauty(new int[][]{{1, 2}, {3, 2}, {2, 1}, {5, 2}, {3, 5}}, new int[]{3, 2, 4, 8});
    }

    public int[] maximumBeauty(int[][] items, int[] queries) {
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        for (int[] item : items) {
            tm.merge(item[0], item[1], (oldVal, newVal) ->
                    newVal.compareTo(oldVal) > 0 ? newVal : oldVal);
        }
        int leftMax = 0;
        for (Map.Entry<Integer, Integer> entry : tm.entrySet()) {
            leftMax = Math.max(leftMax, entry.getValue());
            entry.setValue(leftMax);
        }
        for (int i = 0; i < queries.length; i++) {
            Integer leftKey = tm.floorKey(queries[i]);
            if (leftKey == null) {
                queries[i] = 0;
            } else {
                queries[i] = tm.get(leftKey);
            }
        }
        return queries;
    }
}
